#include<stdio.h>
#include<stdlib.h>

//“带头结点的单向链表”
				
typedef int ElemType;			//数据的类型
typedef struct node				//队列的数据节点的类型
{
	ElemType data;				//数据域 --》存储数据
	struct node *next;			//指针域 --》保存逻辑上的下一个
}Nq;

typedef struct LinkedQueue		//队列的头结点
{
	struct node * front;		//指向队列的第一个节点，队首
	struct node * rear;			//指向队列的最后一个节点，队尾	
	int node_num;				//保存队列的数据元素的个数
}Queue;
/*
队列的基本操作：
InitQueue		初始化队列
EnQueue			入队
DeQueue			出队
QueueLength		获取队列的长度（元素的个数）
GetHead			获取队头元素，但是不出队
IsEmpty			判断队列是否为空
ClearQueue		清空队列
DestroyQueue	销毁队列
*/

//1）初始化一个链式队列					
Queue * InitQueue()
{
	Queue *lq=(Queue*)malloc(sizeof(Queue));
	lq->front=lq->rear=NULL;
	lq->node_num=0;
	return lq;
}

/*
	2）判断队列是否为空
	1	为空
	0	不为空
*/					
int IsEmpty(Queue * lq)
{
	if(lq==NULL||lq->node_num==0)
	{
		return 1;
	}
	return 0;
}
					

//3）求队列的长度，即队列的元素个数
				
int QueueLength(Queue * lq)
{
		if(lq==NULL)
		{
			return 0;
		}
		return lq->node_num;
}
					
/*					
	4）入队 
	1  入队成功
	0  入队失败
*/					
int EnQueue(Queue * lq, ElemType d)
{
	//不能入队的情况：队列不存在
	if(lq==NULL)
	{
		return 0;
	}
	Nq *pnew=(Nq*)malloc(sizeof(Nq));
	pnew->data=d;
	pnew->next=NULL;

	//队尾入队,从无到有
	if(lq->node_num==0)
	{
		lq->front=pnew;
		lq->rear=pnew;
	}
	else
	{
		lq->rear->next=pnew;
		lq->rear=pnew;
	}
	lq->node_num++;
	return 1;
}
					
/*					
5）出队
1	出队成功
0	出队失败
*/				
int DeQueue(Queue * lq, ElemType *d)
{
	//队列为空出队失败
	if(IsEmpty(lq))	
	{
		printf("LinkedQueue is empty \n");
		return 0;
	}
	//出队：先获取队首的数据，再删除队首（第一个节点）
	*d=lq->front->data;

	Nq *p=lq->front;
	lq->front=lq->front->next;
	p->next=NULL;
	free(p);
	lq->node_num--;
	if(lq->node_num==0)
	{
		lq->rear=NULL;
	}
	return 1;
}

/*
	6）获取队首元素的值，但是不出队
	1	获取成功
	0	获取失败
*/					
int GetHead(Queue * lq, ElemType *d)
{
	if(IsEmpty(lq))	
	{
		printf("LinkedQueue is empty \n");
		return 0;
	}
	*d=lq->front->data;
	return 1;
}
						
//7）清空一个队列				
void ClearQueue(Queue * lq)
{				
	//遍历，删除每一个数据节点
	
}
						
//8）销毁一个队列				
void DestroyQueue(Queue * lq)
{
	
	if(IsEmpty(lq))	
	{
		printf("LinkedQueue is empty \n");
		return ;
	}
	//遍历，先删除每一个数据节点，再删除头结点
	Nq *p=lq->front;
	while(p)
	{
		lq->front=lq->front->next;
		p->next=NULL;
		free(p);
		p=lq->front;
	}
	lq->rear=NULL;
	lq->node_num=0;
}

void display(Queue *lq)
{
	Nq *p;
	p=(Nq*)malloc(sizeof(Nq));
	p=lq->front;
	while(p)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
int main()
{
	Queue *lq=InitQueue();
	
	int option;
	int num;
	ElemType data;
	do
	{
		printf("\t1	创建队列\n");
		printf("\t2	向队列中插入元素\n");
		printf("\t3	从队列中删除元素\n");
		printf("\t4	显示队列元素\n");
		printf("\t5	退出\n");
		printf("----------------------------------------------------\n");
		printf("请选择<1,2,3,4,5>:");
		scanf("%d",&option);
		switch(option)
		{
			case 1:
				printf("\n请选择你想要创建元素个数:");
				scanf("%d",&num);
				while(num)
				{
					scanf("%d",&data);
					EnQueue(lq,data);
					num--;
				}
				break;
			case 2:
				printf("请输入你要插入的元素:");
				scanf("%d",&data);
				EnQueue(lq, data);
				break;
			case 3:
				DeQueue(lq,&data);
				printf("x=%d\n",data);
				break;
			case 4: 
				display(lq);
				break;
			case 5: break;
			default:
				printf("输入错误\n");break;
		}
		
	}while(option<=4);

	
	return 0;
}
